/**
 * 题目: 无重复的最长子串
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
 */

/**
 * 1. 创建一个 hash数组记录字符出现的次数(可以只创建 128个, 常用字符)
 * 遍历整个数组, 将他放入 hash里, 若发现次字符出现第二次, 那就更新最大长度,
 * 并从前在遍历一遍数组, 删除字符, 更新出现次数, 当第二次出现字符的次数重新恢复成一时,
 * 继续向前遍历数组...
 * 时间复杂度 O(n^2)  空间复杂度 O(1)
 * (滑动窗口)
 */

public class Main {
    public int lengthOfLongestSubstring(String s) {
        // 定义一个数组用来记录字母出现的次数
        int[] hash = new int[128];

        // 用来记录最长的长度
        int ret = 0;

        // 遍历字符 s
        // 用 right来表示前进, 并将字母存入 hash
        // 用 left来表示当字母不止出现一次时, 来删除字母
        // right - left 表示无重复子串的长度
        for (int left = 0, right = 0; right < s.length(); right++) {

            int in = s.charAt(right);
            // 入窗口
            hash[in]++;

            while (hash[in] > 1) {
                int out = s.charAt(left);

                // 出窗口, 一直出到没有字母重复时结束
                hash[out]--;

                // 更新 left
                left++;
            }
            // 更新结果 (在每次入窗口并检查了已经没有了重复字符时更新)
            // 注意不能再出窗口时更新, 因为有时候没有一个相同的字符, 这时就更新不了最大长度了
            ret = Math.max(right - left + 1, ret);
        }
        return ret;
    }
}
